#!/usr/bin/env python3

from time import time

def min_with_none(val1,val2):
  if val1 == None: return val2
  if val2 == None: return val1
  return min(val1,val2)

def euler82():
  """
  Find the minimal path sum, in matrix.txt (right click and 'Save Link/Target As...'), a 31K text file containing a 80 by 80 matrix, from the left column to the right column.
  """
  matrix = []
  with open("matrix.txt") as file:
    for line in file.readlines():
      matrix.append(list(map(lambda x: [int(x),None],line.strip().split(","))))
  len_matrix = len(matrix)
  for i in range(len_matrix):
    matrix[i][0][1] = matrix[i][0][0]
  for j in range(1,len_matrix):
    for i in range(len_matrix):
      matrix[i][j][1]=min_with_none(matrix[i][j-1][1]+matrix[i][j][0],matrix[i][j][1])
      for k in range(i-1,-1,-1):
        matrix[k][j][1]=min_with_none(matrix[k+1][j][1]+matrix[k][j][0],matrix[k][j][1])
      for k in range(i+1,len_matrix):
        matrix[k][j][1]=min_with_none(matrix[k-1][j][1]+matrix[k][j][0],matrix[k][j][1])

  return min(map(lambda x:x[-1][1],matrix))


          
    
"""
Print answer and process time
"""
if __name__=="__main__":
  time_begin = time()
  print("Answer : {}".format(euler82()))
  print("Time : {}\"".format(time()-time_begin))
